import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;


public class CacheSim {

    public static void main(String[] args) {
        String trace2k = "trace-2k.csv";
        String trace5k = "trace-5k.csv";
        CacheSimulator cacheSim;
        System.out.println("Experiment 1");
        cacheSim = new CacheSimulator(0, 2, 0, trace2k);
        cacheSim.printThis();
        System.out.println("Experiment 2");
        cacheSim = new CacheSimulator(0, 4, 1, trace2k);
        cacheSim.printThis();
        System.out.println("Experiment 3");
        cacheSim = new CacheSimulator(0, 8, 1, trace2k);
        cacheSim.printThis();
        System.out.println("Experiment 4");
        cacheSim = new CacheSimulator(1, 2, 0, trace2k);
        cacheSim.printThis();
        System.out.println("Experiment 5");
        cacheSim = new CacheSimulator(1, 4, 1, trace2k);
        cacheSim.printThis();
        System.out.println("Experiment 6");
        cacheSim = new CacheSimulator(1, 8, 1, trace2k);
        cacheSim.printThis();      
        
        System.out.println("Experiment 1");
        cacheSim = new CacheSimulator(0, 2, 0, trace5k);
        cacheSim.printThis();
        System.out.println("Experiment 2");
        cacheSim = new CacheSimulator(0, 4, 1, trace5k);
        cacheSim.printThis();
        System.out.println("Experiment 3");
        cacheSim = new CacheSimulator(0, 8, 1, trace5k);
        cacheSim.printThis();
        System.out.println("Experiment 4");
        cacheSim = new CacheSimulator(1, 2, 0, trace5k);
        cacheSim.printThis();
        System.out.println("Experiment 5");
        cacheSim = new CacheSimulator(1, 4, 1, trace5k);
        cacheSim.printThis();
        System.out.println("Experiment 6");
        cacheSim = new CacheSimulator(1, 8, 1, trace5k);
        cacheSim.printThis();
      
    }
        
}

class CacheSimulator {

    Cache cacheL1iA, cacheL1dA, cacheL2A; // CPU A
    Cache cacheL1iB, cacheL1dB, cacheL2B; // CPU B
    Cache cacheL3, LM1, LM2; // unified
    int size1LM, size2LM;
    int associativity;
    int cacheLineSize;
    int writePolicy;
    int instructionCount;
    int memAccessCount;
    List<String> arrAddress;
    
    // example: mesiTransitionCounter(3, 2) means from I --> S state
    int[][] mesiTransitionCounter = 
    	//	 M, E, S, I 
    	{ 	{0, 0, 0, 0},   // M  
    		{0, 0, 0, 0}, 	// E
    		{0, 0, 0, 0}, 	// S
    		{0, 0, 0, 0} };	// I
 
    public CacheSimulator(int exp, int assoc, int writePolicy, String filepath) {
        
        if (exp == 0) {
            initializeOption1(assoc, writePolicy);
        } else {
            initializeOption2(assoc, writePolicy);
        }
        instructionCount = 0;
        memAccessCount = 0;
        arrAddress = new ArrayList<String>();
        executeInstructions(filepath);
        
    }
    public CacheSimulator() {
        instructionCount = 0;
        memAccessCount = 0;
        arrAddress = new ArrayList<String>();
        
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("File location of csv trace file:[2k or 5k]\ntrace-");
        String filepath = "trace-";
        try {
            filepath += reader.readLine();
        }
        catch (IOException e1) {
            // TODO Auto-generated catch block
            e1.printStackTrace();
        }
        System.out.println("type: [0: Experiment 1-3 or 1: Experiment 4-6] [associativity (2,4, or 8)] [0: writethrough or 1: writeback]");
        String commands;
        try {
            commands = reader.readLine();
            Scanner s = new Scanner(commands);
            int exp = s.nextInt();
            if (exp == 0) {
                initializeOption1(s.nextInt(), s.nextInt());
            } else if (exp == 1){
            	initializeOption2(s.nextInt(), s.nextInt());
            }
        }
        catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        instructionCount = 0;
        
        filepath += ".csv";
        executeInstructions(filepath);
    }  
    
    
    private void initializeOption1(int theAssociativity, int theWritePolicy) {
        cacheLineSize = 16;
        associativity = theAssociativity;
        writePolicy = theWritePolicy;
        cacheL1iA = new Cache(1, 8, associativity);
        cacheL1dA = new Cache(1, 8, associativity);
        cacheL2A = new Cache(10, 32, associativity);
        cacheL3 = new Cache(20, 128, associativity);    
        LM1 = new Cache(120, 8*1024/cacheLineSize, 1);
        LM2 = new Cache(250, 1024*1024/cacheLineSize, 1);
        
        cacheL1iB = new Cache(1, 8, associativity);
        cacheL1dB = new Cache(1, 8, associativity);
        cacheL2B = new Cache(10, 32, associativity);
    }
    
    private void initializeOption2(int theAssociativity, int theWritePolicy) {
        cacheLineSize = 64;
        associativity = theAssociativity;
        writePolicy = theWritePolicy;
        cacheL1iA = new Cache(2, 16, associativity);
        cacheL1dA = new Cache(2, 16, associativity);
        cacheL2A = new Cache(12, 64, associativity);
        cacheL3 = new Cache(25, 256, associativity);   
        LM1 = new Cache(120, 8*1024/cacheLineSize, 1);
        LM2 = new Cache(250, 1024*1024/cacheLineSize, 1);
        
        cacheL1iB = new Cache(2, 16, associativity);
        cacheL1dB = new Cache(2, 16, associativity);
        cacheL2B = new Cache(12, 64, associativity);
    }
        
    
    private void executeInstructions(String filepath) {    	
        BufferedReader reader = null;
        try {
            FileReader fr = new FileReader(new File(filepath));
            
            reader = new BufferedReader(fr);
            String line = reader.readLine();
            //int counter = 0;
            //while (counter < 50) {
            while (line!=null) {
                arrAddress.add(line);
                line = reader.readLine();
                //counter++;
            }
        } catch (IOException ioe) {
            System.out.println(ioe.getMessage());
        } finally {
            try { if (reader!=null) reader.close(); } catch (Exception e) {}
        }
        
        String addressCPUB = "";
        //int countB = 0;
        for (String line: arrAddress)  {
        	instructionCount++; //increments instructions        	
        	decodeAddress(line, cacheL1iA, cacheL1dA, cacheL2A);   
        	
        	if (instructionCount > 49) {
        		addressCPUB = arrAddress.get(instructionCount-50);
        		decodeAddress(addressCPUB, cacheL1iB, cacheL1dB, cacheL2B); 
        		//countB++;
        		//System.out.println(line + " vs " + addressCPUB);
        	}
        }
        
        for (int i = instructionCount-50; i < instructionCount; i++) {
        	addressCPUB = arrAddress.get(i);
        	decodeAddress(addressCPUB, cacheL1iB, cacheL1dB, cacheL2B); 
        	//countB++;
        }
        
        //System.out.println(countB);
    }
    
    public void decodeAddress(String address, Cache l1i, Cache l1d, Cache l2) {
    	int totalEntries = l1d.associativeEntries + l2.associativeEntries + cacheL3.associativeEntries - 1;
    	
    	String[] tokens = address.split(",");            
        int i = Integer.parseInt(tokens[0]); // instruction address
        int j = 2; // leave it at 2 if there is no read/write value
        int k = 2; // leave it at 2 if there is no read/write value            
        if (tokens.length > 1) {                    
            j = Integer.parseInt(tokens[1]); // read or write
            k = Integer.parseInt(tokens[2]); // data address
        }
                   
        // instruction cache
        cacheRead(l1i, i);
       
        // data cache (read)
        if (j == 0) {
        	memAccessCount++;
            if (i % totalEntries < l1d.associativeEntries) {
            	cacheRead(l1d, i);
            } else if (i % totalEntries < (l1d.associativeEntries + l2.associativeEntries)) {
            	l1d.misses++;
            	cacheRead(l2, i);
            } else {
            	l1d.misses++;
            	l2.misses++;
            	cacheRead(cacheL3, i);
            }
        } else if (j == 1) { // data cache (write)
        	memAccessCount++;
        	if (writePolicy == 0) { // writethrough
            	cacheWrite(l1d, i);
            	cacheWrite(l2, i);
            	cacheWrite(cacheL3, i);
            	cacheWriteMem(i);

        	} else if (writePolicy == 1) { // writeback
        		cacheWrite(l1d, i);
        	}
        }
    }
    
    
    public void cacheRead(Cache cache, int address) {
        int set = (address / cacheLineSize) % cache.associativeEntries;
        int tag = address / (cacheLineSize * cache.associativeEntries); 
        int memAddress = address % (LM1.cacheEntries + LM2.cacheEntries -1);
        
        
   
        boolean found = false;
    
        for (int i = 0; i < associativity; i++) { // READ HIT
            if (cache.entry[set][i].tag == tag && cache.entry[set][i].mesi != 3) {            	 
                found = true;
                cache.hits++;
                mesiTransitionCounter[cache.entry[set][i].mesi][cache.entry[set][i].mesi]++;
                break;
            }
        }        
               
        if (!found) {       // READ MISS
            int randAdd = 0;
            Random rand = new Random();
            randAdd = rand.nextInt(Integer.MAX_VALUE) % associativity;
            cache.misses++;

            cache.entry[set][randAdd].tag = tag;
            if (writePolicy == 0) {
                snoop(address);
                mesiTransitionCounter[cache.entry[set][randAdd].mesi][2]++;
                cache.entry[set][randAdd].mesi = 2;
            } else {
                mesiTransitionCounter[cache.entry[set][randAdd].mesi][1]++;
                cache.entry[set][randAdd].mesi = 1;
            }
            
            if (memAddress < LM1.cacheEntries) { //data should be in 1LM
                LM1.entry[memAddress][0].tag = tag;
                LM1.hits++;
                mesiTransitionCounter[LM1.entry[memAddress][0].mesi][1]++;
                LM1.entry[memAddress][0].mesi = 1;
            } else {
                LM2.entry[memAddress-LM1.associativeEntries][0].tag = tag;
                LM2.hits++;
                mesiTransitionCounter[LM2.entry[memAddress-LM1.associativeEntries][0].mesi][1]++;
                LM2.entry[memAddress-LM1.associativeEntries][0].mesi = 1;
            }   
        }
    }
        
    private void cacheWrite(Cache cache, int address) {      
    	 
        int set = (address / cacheLineSize) % cache.associativeEntries;
        int tag = address / (cacheLineSize * cache.associativeEntries); 
        
//        boolean found = false;
//
//        for (int i = 0; i < associativity; i++) { // WRITE HIT
//            if (cache.entry[set][i].tag == tag) {
//                found = true;
//                cache.hits++;
//                
//                if (cache.entry[set][i].mesi != 3) {
//                    mesiTransitionCounter[cache.entry[set][i].mesi][0]++;
//                    cache.entry[set][i].mesi = 0;
//                    snoop(address);
//                }
//                break;
//            }
//        }    

            int randAdd = 0;
            Random rand = new Random();
            randAdd = rand.nextInt(Integer.MAX_VALUE) % associativity;
            
            cache.entry[set][randAdd].tag = tag;
            mesiTransitionCounter[cache.entry[set][randAdd].mesi][0]++;
            if (cache.entry[set][randAdd].mesi == 3) {
                cache.misses++;
            } else {
                cache.hits++;
                if (cache.entry[set][randAdd].mesi == 2) {
                    snoop(address);
                }
            }
            mesiTransitionCounter[cache.entry[set][randAdd].mesi][0]++;
            cache.entry[set][randAdd].mesi = 0;
          
       }
    
    private void cacheWriteMem(int address) {    	



    	Cache c;
    	
    	int memAddress = (address / cacheLineSize) % (LM1.associativeEntries + LM2.associativeEntries -1);
    	if (memAddress < LM1.cacheEntries) { //data should be in 1LM
            c = LM1;
        } else { //data is in 2LM
            c = LM2;
        }
        int set = (address / cacheLineSize) % c.associativeEntries;
        int tag = address / (cacheLineSize * c.associativeEntries); 

        c.entry[set][0].tag = tag;
        if (c.entry[set][0].mesi == 3) {
            c.misses++;
        } else {
            c.hits++;
            if (c.entry[set][0].mesi == 2) {
                snoop(address);
            }
        }
        mesiTransitionCounter[c.entry[set][0].mesi][0]++;
        c.entry[set][0].mesi = 0;
    }
    
    
    private void snoop(int address) {
        Cache[] caches = {cacheL1iA, cacheL1dA, cacheL2A, cacheL1iB, cacheL1dB, cacheL2B, cacheL3, LM1, LM2};
        for (int i = 0; i < caches.length-2; i++) {
            Cache c = caches[i];
            int set = (address / cacheLineSize) % c.associativeEntries;
            for (int j = 0; j < associativity; j++) {
                if (c.entry[set][j].tag == address / (cacheLineSize * c.associativeEntries)
                                && c.entry[set][0].mesi == 2) {
                    mesiTransitionCounter[c.entry[set][j].mesi][3]++;
                    c.entry[set][j].mesi = 3;
                }
            }   
        }
        for (int i = caches.length-2; i < caches.length; i++) {
            Cache c = caches[i];
            int set = (address / cacheLineSize) % c.associativeEntries;
            if (c.entry[set][0].tag == address / (cacheLineSize * c.associativeEntries) 
                            && c.entry[set][0].mesi == 2) {
                mesiTransitionCounter[c.entry[set][0].mesi][3]++;
                c.entry[set][0].mesi = 3;
            }
        }
    }
    public int getTotalStallCycles() {
        return cacheL1iA.misses * cacheL1iA.latency
                        + cacheL1dA.misses * cacheL1dA.latency
                        + cacheL2A.misses * cacheL2A.latency
                        + cacheL1iB.misses * cacheL1iB.latency
                        + cacheL1dB.misses * cacheL1dB.latency
                        + cacheL2B.misses * cacheL2B.latency
                        + cacheL3.misses * cacheL3.latency
                        + LM1.misses * LM1.latency
                        + LM2.misses * LM2.latency;
                      
    }
    
    public void printThis() {
        
        System.out.println("--------------------------------------------------");
        System.out.println();
        System.out.println("Instruction Count (CPU A + CPU B): " + instructionCount*2);
        System.out.println("Memory Access Count: " + memAccessCount);
        System.out.println("total stall cycles: " + getTotalStallCycles());
        
        System.out.println("\nCPU A: ===========================================");
        
        System.out.println("L1i Hits: " +  cacheL1iA.hits);
        System.out.println("L1i Misses: " +  cacheL1iA.misses);
        
        System.out.println("L1d Hits: " +  cacheL1dA.hits);
        System.out.println("L1d Misses: " +  cacheL1dA.misses);
        
        System.out.println("L2 Hits: " +  cacheL2A.hits);
        System.out.println("L2 Misses: " +  cacheL2A.misses);
        
        System.out.println("\nCPU B: ===========================================");
        
        System.out.println("L1i Hits: " +  cacheL1iB.hits);
        System.out.println("L1i Misses: " +  cacheL1iB.misses);
        
        System.out.println("L1d Hits: " +  cacheL1dA.hits);
        System.out.println("L1d Misses: " +  cacheL1dB.misses);
        
        System.out.println("L2 Hits: " +  cacheL2A.hits);
        System.out.println("L2 Misses: " +  cacheL2B.misses);
        
        System.out.println("\n=================================================");
        
        System.out.println("L3 Hits: " +  cacheL1dA.hits);
        System.out.println("L3 Misses: " +  cacheL3.misses);
        
        System.out.println("LM1 Hits: " +  LM1.hits);
        System.out.println("LM1 Misses: " +  LM1.misses);
        
        System.out.println("LM2 Hits: " +  LM2.hits);
        System.out.println("LM2 Misses: " +  LM2.misses);
        System.out.println("--------------------------------------------------\n");
        System.out.println("MESI Transition Table\n");
        for (int i = 0; i < 4; i++) {
            System.out.print("(");
            for (int j = 0; j < 4; j++) {
                System.out.print( mesiTransitionCounter[i][j] + ", " );
            }
            System.out.print(")\n");
        }
        

    }
        

    
}

class Cache {
    int misses;
    int hits;
    int checked;
    final int latency;
    int cacheEntries;
    int associativeEntries;
    CacheEntry[][] entry;
    
    public Cache(int theLatency, int theEntries, int theAssociativity) {
        misses = 0;
        hits = 0;
        checked = 0;
        latency = theLatency;
        cacheEntries = theEntries;
        associativeEntries = theEntries / theAssociativity;
        //System.out.println(associativeEntries);
        entry = new CacheEntry[associativeEntries][theAssociativity];
        
        for (int i = 0; i < associativeEntries; i++) {
        	for (int j = 0; j < theAssociativity; j++) {
        		entry[i][j] = new CacheEntry();
            }
        }
        
    }
    
}

class CacheEntry {
    int tag;
    int mesi;
    
    public CacheEntry() {
    	tag = 0; 	
    	mesi = 3;
    }
}



